package com.atwulidun.iterativetree;


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class IterativeTreeDemo {
    public static void main(String[] args) {
        // 一、首先创建一棵二叉树
        IterativeTree tree = new IterativeTree();
        // 二、创建相应的根结点和左右结点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        // 三、将左右结点依次挂在根结点上
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node4);
        node3.setRight(node5);
        // 四、将外部创建好的数的根结点传入到binaryTree
        tree.setRoot(root);

        // 五、遍历
        // 1.深度优先前序遍历
        // 递归前序遍历
        System.out.println("递归前序遍历：");// 1 2 3 4 5
        tree.preOrder();
        // 单栈前序遍历
        System.out.println("单栈前序遍历：");
        tree.iterativePreOrder();
        System.out.println();
        System.out.println("====================================");

        // 2.深度优先中序遍历
        // 递归中序遍历
        System.out.println("递归中序遍历：");// 2 1 4 3 5
        tree.infixOrder();
        // 单栈中序遍历
        System.out.println("单栈中序遍历：");
        tree.iterativeInfixOrder();
        System.out.println();
        System.out.println("====================================");

        // 3.深度优先后序遍历
        // 递归后序遍历
        System.out.println("递归后序遍历：");// 2 4 5 3 1
        tree.postOrder();
        // 单栈后序遍历
        System.out.println("单栈后序遍历：");
        tree.iterativePostOrder1();
        System.out.println();
        // 双栈后序遍历
        System.out.println("双栈后序遍历：");
        tree.iterativePostOrder2();
        System.out.println();
        System.out.println("====================================");

        // 4.广度优先遍历
        System.out.println("广度优先遍历：");
        tree.bfs();

    }
}

class IterativeTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    // 下面的三个遍历方法将HeroNode中的三个方法包装一下，因为这里面要加入对root是否为空的判断，
    // 如果在这里进行递归调用的话，那么这个判断就会破坏递归的结构性
    // 前序遍历
    public void preOrder() {
        if (root == null) {
            System.out.println("二叉树为空！");
        } else {
            root.preOrder();
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (root == null) {
            System.out.println("二叉树为空！");
        } else {
            root.infixOrder();
        }
    }

    // 后序遍历
    public void postOrder() {
        if (root == null) {
            System.out.println("二叉树为空！");
        } else {
            root.postOrder();
        }
    }

    // 以下四个方法为二叉树的深度优先遍历方法(用栈实现)
    // 1.前序遍历
    public void iterativePreOrder() {
        if (root == null) {
            System.out.println("树为空，不能遍历！");
            return;
        }
        // 创建一个栈
        Deque<HeroNode> stack = new LinkedList<>();
        // 将当前根结点先压栈
        stack.push(root);
        // 定义一个临时结点
        HeroNode temp;
        while (!stack.isEmpty()) {
            // 弹栈
            temp = stack.pop();
            // 输出出栈元素内容
            System.out.print(temp.getNo() + "->");
            // 先把temp的右子结点压栈，再把左子结点压栈，这样左子结点先弹出来
            // 如果temp存在右子结点
            if (temp.getRight() != null) {
                stack.push(temp.getRight());
            }
            // 如果temp存在左子结点
            if (temp.getLeft() != null) {
                stack.push(temp.getLeft());
            }
        }
    }

    // 2.中序遍历
    public void iterativeInfixOrder() {
        if (root == null) {
            System.out.println("树为空，不能遍历！");
            return;
        }
        // 建一个栈
        Deque<HeroNode> stack = new LinkedList<>();
        // 定义一个临时变量
        HeroNode node = root;
        while (node != null || !stack.isEmpty()) {
            // 将根结点和左子结点连续压栈
            while (node != null) {
                stack.push(node);
                node = node.getLeft();
            }
            // 如果栈不为空，弹栈
            if (!stack.isEmpty()) {
                node = stack.pop();
                // 输出出栈元素
                System.out.print(node.getNo() + "->");
                // 处理node的右子树
                // 如果node的右子树为空，那么是通过!stack.isEmpty()再次进入外层的while循环
                node = node.getRight();
            }
        }
    }

    // 3.后序遍历(单栈)
    public void iterativePostOrder1() {
        if (root == null) {
            System.out.println("树为空，不能遍历！");
            return;
        }
        // 建一个栈
        Deque<HeroNode> stack = new LinkedList<>();
        // 定义一个临时变量
        HeroNode node = root;
        // 定义一个变量来保存上一个被处理的结点
        HeroNode preNode = null;
        while (node != null || !stack.isEmpty()) {
            // 将根结点和左子结点连续压栈
            while (node != null) {
                stack.push(node);
                node = node.getLeft();
            }
            // 如果栈不为空，弹栈，但是在处理弹出来的元素之前要判断：
            // 该元素是否没有右结点，或右结点在上一次已经被处理。因为每次都是弹出左子结点，必须要对其右子结点进行判断
            if (!stack.isEmpty()) {
                // 定义一个临时变量来保存弹出元素的右子结点
                // 注意：这里是先看一下，要用peek
                HeroNode right = stack.peek().getRight();
                // 如果弹出元素没有右子结点或者右子结点是上一个被处理的结点
                // 可以对当前出栈元素进行处理
                if (right == null || right == preNode) {
                    node = stack.pop();
                    // 打印出当前出栈的元素
                    System.out.print(node.getNo() + "->");
                    // 将当前元素标记为上一个被处理的结点
                    preNode = node;
                    // 此时可以再次进入外层while循环对上一个左子结点进行peek查看了，是以!stack.isEmpty()的条件进入循环的，
                    // 因此要将node置为null，不然会优先以node != null进入循环，再把node压栈
                    node = null;
                } else {
                    // 如果弹出元素有右子结点且右子结点不是上一个被处理的结点，那么先处理该右子结点
                    node = right;
                }
            }
        }
    }

    // 4.后序遍历(双栈)
    // 前序遍历：根 -> 左 -> 右
    // 轴对称前序遍历：根 -> 右 -> 左
    // 逆轴对称前序遍历(即为后序遍历)：左 -> 右 -> 根
    public void iterativePostOrder2() {
        if (root == null) {
            System.out.println("树为空，不能遍历！");
            return;
        }
        // 定义两个栈，一个用于轴对称前序遍历，一个用于对轴对称前序遍历进行逆序输出
        Deque<HeroNode> stack = new LinkedList<>();
        Deque<HeroNode> printOut = new LinkedList<>();
        // 下面模拟轴对称前序遍历的过程
        // 将当前根结点先压栈
        stack.push(root);
        // 定义一个临时结点
        HeroNode temp;
        while (!stack.isEmpty()) {
            // 弹栈
            temp = stack.pop();
            // 本来为输出出栈元素内容，但这里将其压入printOut中，最先输出的反而变成最后输出
            printOut.push(temp);
            // 先把temp的左子结点压栈，再把右子结点压栈，这样右子结点先弹出来
            // 如果temp存在左子结点
            if (temp.getLeft() != null) {
                stack.push(temp.getLeft());
            }
            // 如果temp存在右子结点
            if (temp.getRight() != null) {
                stack.push(temp.getRight());
            }
        }
        // 最后再把printOut的元素依次弹出并输出即可
        while (!printOut.isEmpty()) {
            System.out.print(printOut.pop().getNo() + "->");
        }
    }

    // 以下为二叉树的广度优先遍历(用队列实现)
    public void bfs() {
        if (root == null) {
            System.out.println("树为空，不能遍历！");
            return;
        }
        // 定义一个队列
        Queue<HeroNode> queue = new LinkedList<>();
        // 根结点进队列
        queue.offer(root);
        // 定义一个临时变量
        HeroNode temp;
        while (!queue.isEmpty()) {
            // 出队列
            temp = queue.poll();
            // 打印出队列的元素
            System.out.print(temp.getNo() + "->");
            // 若出队列元素的左子结点不为空，将其入队列
            if (temp.getLeft() != null) {
                queue.offer(temp.getLeft());
            }
            // 若出队列元素的右子结点不为空，将其入队列
            if (temp.getRight() != null) {
                queue.offer(temp.getRight());
            }
        }
    }


}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;// 默认为null
    private HeroNode right;// 默认为null

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    // 以下三种遍历的方法都是把当前结点当成是根结点
    // 前序遍历：根 左 右
    public void preOrder() {
        System.out.println(this);
        if (left != null) {
            // 又把左节点当成一个根结点
            left.preOrder();
        }
        if (right != null) {
            // 又把右节点当成一个根结点
            right.preOrder();
        }
    }

    // 中序遍历：左 根 右
    public void infixOrder() {
        if (left != null) {
            left.infixOrder();
        }
        System.out.println(this);
        if (right != null) {
            right.infixOrder();
        }
    }

    // 后序遍历：左 右 根
    public void postOrder() {
        if (left != null) {
            left.postOrder();
        }
        if (right != null) {
            right.postOrder();
        }
        System.out.println(this);
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}